// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
 *******************************************************************************
 * Copyright (C) 2013-2014, International Business Machines
 * Corporation and others.  All Rights Reserved.
 *******************************************************************************
 * CollationRootElements.java, ported from collationrootelements.h/.cpp
 *
 * C++ version created on: 2013mar01
 * created by: Markus W. Scherer
 */

package com.ibm.icu.impl.coll;

/**
 * Container and access methods for collation elements and weights that occur in the root collator.
 * Needed for finding boundaries for building a tailoring.
 *
 * <p>This class takes and returns 16-bit secondary and tertiary weights.
 */
public final class CollationRootElements {
    public CollationRootElements(long[] rootElements) {
        elements = rootElements;
    }

    /** Higher than any root primary. */
    public static final long PRIMARY_SENTINEL = 0xffffff00L;

    /**
     * Flag in a root element, set if the element contains secondary & tertiary weights, rather than
     * a primary.
     */
    public static final int SEC_TER_DELTA_FLAG = 0x80;

    /** Mask for getting the primary range step value from a primary-range-end element. */
    public static final int PRIMARY_STEP_MASK = 0x7f;

    /**
     * Index of the first CE with a non-zero tertiary weight. Same as the start of the compact root
     * elements table.
     */
    public static final int IX_FIRST_TERTIARY_INDEX = 0;

    /** Index of the first CE with a non-zero secondary weight. */
    static final int IX_FIRST_SECONDARY_INDEX = 1;

    /** Index of the first CE with a non-zero primary weight. */
    static final int IX_FIRST_PRIMARY_INDEX = 2;

    /** Must match Collation.COMMON_SEC_AND_TER_CE. */
    static final int IX_COMMON_SEC_AND_TER_CE = 3;

    /**
     * Secondary & tertiary boundaries. Bits 31..24: [fixed last secondary common byte 45] Bits
     * 23..16: [fixed first ignorable secondary byte 80] Bits 15.. 8: reserved, 0 Bits 7.. 0: [fixed
     * first ignorable tertiary byte 3C]
     */
    static final int IX_SEC_TER_BOUNDARIES = 4;

    /** The current number of indexes. Currently the same as elements[IX_FIRST_TERTIARY_INDEX]. */
    static final int IX_COUNT = 5;

    /**
     * Returns the boundary between tertiary weights of primary/secondary CEs and those of tertiary
     * CEs. This is the upper limit for tertiaries of primary/secondary CEs. This minus one is the
     * lower limit for tertiaries of tertiary CEs.
     */
    public int getTertiaryBoundary() {
        return ((int) elements[IX_SEC_TER_BOUNDARIES] << 8) & 0xff00;
    }

    /** Returns the first assigned tertiary CE. */
    long getFirstTertiaryCE() {
        return elements[(int) elements[IX_FIRST_TERTIARY_INDEX]] & ~SEC_TER_DELTA_FLAG;
    }

    /** Returns the last assigned tertiary CE. */
    long getLastTertiaryCE() {
        return elements[(int) elements[IX_FIRST_SECONDARY_INDEX] - 1] & ~SEC_TER_DELTA_FLAG;
    }

    /**
     * Returns the last common secondary weight. This is the lower limit for secondaries of primary
     * CEs.
     */
    public int getLastCommonSecondary() {
        return ((int) elements[IX_SEC_TER_BOUNDARIES] >> 16) & 0xff00;
    }

    /**
     * Returns the boundary between secondary weights of primary CEs and those of secondary CEs.
     * This is the upper limit for secondaries of primary CEs. This minus one is the lower limit for
     * secondaries of secondary CEs.
     */
    public int getSecondaryBoundary() {
        return ((int) elements[IX_SEC_TER_BOUNDARIES] >> 8) & 0xff00;
    }

    /** Returns the first assigned secondary CE. */
    long getFirstSecondaryCE() {
        return elements[(int) elements[IX_FIRST_SECONDARY_INDEX]] & ~SEC_TER_DELTA_FLAG;
    }

    /** Returns the last assigned secondary CE. */
    long getLastSecondaryCE() {
        return elements[(int) elements[IX_FIRST_PRIMARY_INDEX] - 1] & ~SEC_TER_DELTA_FLAG;
    }

    /** Returns the first assigned primary weight. */
    long getFirstPrimary() {
        return elements[(int) elements[IX_FIRST_PRIMARY_INDEX]]; // step=0: cannot be a range end
    }

    /** Returns the first assigned primary CE. */
    long getFirstPrimaryCE() {
        return Collation.makeCE(getFirstPrimary());
    }

    /**
     * Returns the last root CE with a primary weight before p. Intended only for reordering group
     * boundaries.
     */
    long lastCEWithPrimaryBefore(long p) {
        if (p == 0) {
            return 0;
        }
        assert (p > elements[(int) elements[IX_FIRST_PRIMARY_INDEX]]);
        int index = findP(p);
        long q = elements[index];
        long secTer;
        if (p == (q & 0xffffff00L)) {
            // p == elements[index] is a root primary. Find the CE before it.
            // We must not be in a primary range.
            assert ((q & PRIMARY_STEP_MASK) == 0);
            secTer = elements[index - 1];
            if ((secTer & SEC_TER_DELTA_FLAG) == 0) {
                // Primary CE just before p.
                p = secTer & 0xffffff00L;
                secTer = Collation.COMMON_SEC_AND_TER_CE;
            } else {
                // secTer = last secondary & tertiary for the previous primary
                index -= 2;
                for (; ; ) {
                    p = elements[index];
                    if ((p & SEC_TER_DELTA_FLAG) == 0) {
                        p &= 0xffffff00L;
                        break;
                    }
                    --index;
                }
            }
        } else {
            // p > elements[index] which is the previous primary.
            // Find the last secondary & tertiary weights for it.
            p = q & 0xffffff00L;
            secTer = Collation.COMMON_SEC_AND_TER_CE;
            for (; ; ) {
                q = elements[++index];
                if ((q & SEC_TER_DELTA_FLAG) == 0) {
                    // We must not be in a primary range.
                    assert ((q & PRIMARY_STEP_MASK) == 0);
                    break;
                }
                secTer = q;
            }
        }
        return (p << 32) | (secTer & ~SEC_TER_DELTA_FLAG);
    }

    /**
     * Returns the first root CE with a primary weight of at least p. Intended only for reordering
     * group boundaries.
     */
    long firstCEWithPrimaryAtLeast(long p) {
        if (p == 0) {
            return 0;
        }
        int index = findP(p);
        if (p != (elements[index] & 0xffffff00L)) {
            for (; ; ) {
                p = elements[++index];
                if ((p & SEC_TER_DELTA_FLAG) == 0) {
                    // First primary after p. We must not be in a primary range.
                    assert ((p & PRIMARY_STEP_MASK) == 0);
                    break;
                }
            }
        }
        // The code above guarantees that p has at most 3 bytes: (p & 0xff) == 0.
        return (p << 32) | Collation.COMMON_SEC_AND_TER_CE;
    }

    /** Returns the primary weight before p. p must be greater than the first root primary. */
    long getPrimaryBefore(long p, boolean isCompressible) {
        int index = findPrimary(p);
        int step;
        long q = elements[index];
        if (p == (q & 0xffffff00L)) {
            // Found p itself. Return the previous primary.
            // See if p is at the end of a previous range.
            step = (int) q & PRIMARY_STEP_MASK;
            if (step == 0) {
                // p is not at the end of a range. Look for the previous primary.
                do {
                    p = elements[--index];
                } while ((p & SEC_TER_DELTA_FLAG) != 0);
                return p & 0xffffff00L;
            }
        } else {
            // p is in a range, and not at the start.
            long nextElement = elements[index + 1];
            assert (isEndOfPrimaryRange(nextElement));
            step = (int) nextElement & PRIMARY_STEP_MASK;
        }
        // Return the previous range primary.
        if ((p & 0xffff) == 0) {
            return Collation.decTwoBytePrimaryByOneStep(p, isCompressible, step);
        } else {
            return Collation.decThreeBytePrimaryByOneStep(p, isCompressible, step);
        }
    }

    /** Returns the secondary weight before [p, s]. */
    int getSecondaryBefore(long p, int s) {
        int index;
        int previousSec, sec;
        if (p == 0) {
            index = (int) elements[IX_FIRST_SECONDARY_INDEX];
            // Gap at the beginning of the secondary CE range.
            previousSec = 0;
            sec = (int) (elements[index] >> 16);
        } else {
            index = findPrimary(p) + 1;
            previousSec = Collation.BEFORE_WEIGHT16;
            sec = (int) getFirstSecTerForPrimary(index) >>> 16;
        }
        assert (s >= sec);
        while (s > sec) {
            previousSec = sec;
            assert ((elements[index] & SEC_TER_DELTA_FLAG) != 0);
            sec = (int) (elements[index++] >> 16);
        }
        assert (sec == s);
        return previousSec;
    }

    /** Returns the tertiary weight before [p, s, t]. */
    int getTertiaryBefore(long p, int s, int t) {
        assert ((t & ~Collation.ONLY_TERTIARY_MASK) == 0);
        int index;
        int previousTer;
        long secTer;
        if (p == 0) {
            if (s == 0) {
                index = (int) elements[IX_FIRST_TERTIARY_INDEX];
                // Gap at the beginning of the tertiary CE range.
                previousTer = 0;
            } else {
                index = (int) elements[IX_FIRST_SECONDARY_INDEX];
                previousTer = Collation.BEFORE_WEIGHT16;
            }
            secTer = elements[index] & ~SEC_TER_DELTA_FLAG;
        } else {
            index = findPrimary(p) + 1;
            previousTer = Collation.BEFORE_WEIGHT16;
            secTer = getFirstSecTerForPrimary(index);
        }
        long st = ((long) s << 16) | t;
        while (st > secTer) {
            if ((int) (secTer >> 16) == s) {
                previousTer = (int) secTer;
            }
            assert ((elements[index] & SEC_TER_DELTA_FLAG) != 0);
            secTer = elements[index++] & ~SEC_TER_DELTA_FLAG;
        }
        assert (secTer == st);
        return previousTer & 0xffff;
    }

    /** Finds the index of the input primary. p must occur as a root primary, and must not be 0. */
    int findPrimary(long p) {
        // Requirement: p must occur as a root primary.
        assert ((p & 0xff) == 0); // at most a 3-byte primary
        int index = findP(p);
        // If p is in a range, then we just assume that p is an actual primary in this range.
        // (Too cumbersome/expensive to check.)
        // Otherwise, it must be an exact match.
        assert (isEndOfPrimaryRange(elements[index + 1]) || p == (elements[index] & 0xffffff00L));
        return index;
    }

    /**
     * Returns the primary weight after p where index=findPrimary(p). p must be at least the first
     * root primary.
     */
    long getPrimaryAfter(long p, int index, boolean isCompressible) {
        assert (p == (elements[index] & 0xffffff00L) || isEndOfPrimaryRange(elements[index + 1]));
        long q = elements[++index];
        int step;
        if ((q & SEC_TER_DELTA_FLAG) == 0 && (step = (int) q & PRIMARY_STEP_MASK) != 0) {
            // Return the next primary in this range.
            if ((p & 0xffff) == 0) {
                return Collation.incTwoBytePrimaryByOffset(p, isCompressible, step);
            } else {
                return Collation.incThreeBytePrimaryByOffset(p, isCompressible, step);
            }
        } else {
            // Return the next primary in the list.
            while ((q & SEC_TER_DELTA_FLAG) != 0) {
                q = elements[++index];
            }
            assert ((q & PRIMARY_STEP_MASK) == 0);
            return q;
        }
    }

    /**
     * Returns the secondary weight after [p, s] where index=findPrimary(p) except use index=0 for
     * p=0.
     *
     * <p>Must return a weight for every root [p, s] as well as for every weight returned by
     * getSecondaryBefore(). If p!=0 then s can be BEFORE_WEIGHT16.
     *
     * <p>Exception: [0, 0] is handled by the CollationBuilder: Both its lower and upper boundaries
     * are special.
     */
    int getSecondaryAfter(int index, int s) {
        long secTer;
        int secLimit;
        if (index == 0) {
            // primary = 0
            assert (s != 0);
            index = (int) elements[IX_FIRST_SECONDARY_INDEX];
            secTer = elements[index];
            // Gap at the end of the secondary CE range.
            secLimit = 0x10000;
        } else {
            assert (index >= (int) elements[IX_FIRST_PRIMARY_INDEX]);
            secTer = getFirstSecTerForPrimary(index + 1);
            // If this is an explicit sec/ter unit, then it will be read once more.
            // Gap for secondaries of primary CEs.
            secLimit = getSecondaryBoundary();
        }
        for (; ; ) {
            int sec = (int) (secTer >> 16);
            if (sec > s) {
                return sec;
            }
            secTer = elements[++index];
            if ((secTer & SEC_TER_DELTA_FLAG) == 0) {
                return secLimit;
            }
        }
    }

    /**
     * Returns the tertiary weight after [p, s, t] where index=findPrimary(p) except use index=0 for
     * p=0.
     *
     * <p>Must return a weight for every root [p, s, t] as well as for every weight returned by
     * getTertiaryBefore(). If s!=0 then t can be BEFORE_WEIGHT16.
     *
     * <p>Exception: [0, 0, 0] is handled by the CollationBuilder: Both its lower and upper
     * boundaries are special.
     */
    int getTertiaryAfter(int index, int s, int t) {
        long secTer;
        int terLimit;
        if (index == 0) {
            // primary = 0
            if (s == 0) {
                assert (t != 0);
                index = (int) elements[IX_FIRST_TERTIARY_INDEX];
                // Gap at the end of the tertiary CE range.
                terLimit = 0x4000;
            } else {
                index = (int) elements[IX_FIRST_SECONDARY_INDEX];
                // Gap for tertiaries of primary/secondary CEs.
                terLimit = getTertiaryBoundary();
            }
            secTer = elements[index] & ~SEC_TER_DELTA_FLAG;
        } else {
            assert (index >= (int) elements[IX_FIRST_PRIMARY_INDEX]);
            secTer = getFirstSecTerForPrimary(index + 1);
            // If this is an explicit sec/ter unit, then it will be read once more.
            terLimit = getTertiaryBoundary();
        }
        long st = (((long) s & 0xffffffffL) << 16) | t;
        for (; ; ) {
            if (secTer > st) {
                assert ((secTer >> 16) == s);
                return (int) secTer & 0xffff;
            }
            secTer = elements[++index];
            // No tertiary greater than t for this primary+secondary.
            if ((secTer & SEC_TER_DELTA_FLAG) == 0 || (secTer >> 16) > s) {
                return terLimit;
            }
            secTer &= ~SEC_TER_DELTA_FLAG;
        }
    }

    /** Returns the first secondary & tertiary weights for p where index=findPrimary(p)+1. */
    private long getFirstSecTerForPrimary(int index) {
        long secTer = elements[index];
        if ((secTer & SEC_TER_DELTA_FLAG) == 0) {
            // No sec/ter delta.
            return Collation.COMMON_SEC_AND_TER_CE;
        }
        secTer &= ~SEC_TER_DELTA_FLAG;
        if (secTer > Collation.COMMON_SEC_AND_TER_CE) {
            // Implied sec/ter.
            return Collation.COMMON_SEC_AND_TER_CE;
        }
        // Explicit sec/ter below common/common.
        return secTer;
    }

    /**
     * Finds the largest index i where elements[i]<=p. Requires first primary<=p<0xffffff00
     * (PRIMARY_SENTINEL). Does not require that p is a root collator primary.
     */
    private int findP(long p) {
        // p need not occur as a root primary.
        // For example, it might be a reordering group boundary.
        assert ((p >> 24) != Collation.UNASSIGNED_IMPLICIT_BYTE);
        // modified binary search
        int start = (int) elements[IX_FIRST_PRIMARY_INDEX];
        assert (p >= elements[start]);
        int limit = elements.length - 1;
        assert (elements[limit] >= PRIMARY_SENTINEL);
        assert (p < elements[limit]);
        while ((start + 1) < limit) {
            // Invariant: elements[start] and elements[limit] are primaries,
            // and elements[start]<=p<=elements[limit].
            int i = (int) (((long) start + (long) limit) / 2);
            long q = elements[i];
            if ((q & SEC_TER_DELTA_FLAG) != 0) {
                // Find the next primary.
                int j = i + 1;
                for (; ; ) {
                    if (j == limit) {
                        break;
                    }
                    q = elements[j];
                    if ((q & SEC_TER_DELTA_FLAG) == 0) {
                        i = j;
                        break;
                    }
                    ++j;
                }
                if ((q & SEC_TER_DELTA_FLAG) != 0) {
                    // Find the preceding primary.
                    j = i - 1;
                    for (; ; ) {
                        if (j == start) {
                            break;
                        }
                        q = elements[j];
                        if ((q & SEC_TER_DELTA_FLAG) == 0) {
                            i = j;
                            break;
                        }
                        --j;
                    }
                    if ((q & SEC_TER_DELTA_FLAG) != 0) {
                        // No primary between start and limit.
                        break;
                    }
                }
            }
            if (p < (q & 0xffffff00L)) { // Reset the "step" bits of a range end primary.
                limit = i;
            } else {
                start = i;
            }
        }
        return start;
    }

    private static boolean isEndOfPrimaryRange(long q) {
        return (q & SEC_TER_DELTA_FLAG) == 0 && (q & PRIMARY_STEP_MASK) != 0;
    }

    /** Data structure: See ICU4C source/i18n/collationrootelements.h. */
    private long[] elements;
}
